/***************************************************************************
 *   Copyright (C) Catedra de structuri de date				   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/


#include <stdio.h>
#include <malloc.h>
#include "binarytree.h"


/**
 * Data Structures and typedefs   
 */

struct _BT_Node{
	struct _BT_Node * sons[2], *parent;
	void  * data;
};


struct BinaryTree_adt{
	BT_Node        root;
	BT_Allocator   alloc;
	BT_Deallocator dealloc;	
};

/**
 *  Constructora and Destructors  
 */

BinaryTree BT_New(void ){
	BinaryTree BT_ret = (BinaryTree) malloc(sizeof(struct BinaryTree_adt));
	
	BT_ret->alloc = NULL;	
	BT_ret->dealloc = NULL;	
	BT_ret->root = BT_NULL;
	return BT_ret;
}

BT_Node BT_NewNode( BinaryTree a, void * data, BT_Node left, BT_Node right, BT_Node parent, int dir){
	BT_Node  BT_ret;
	
	if ( a  == NULL || a->alloc == NULL )
		BT_ret = (BT_Node) malloc( sizeof( struct _BT_Node));	
	else
		BT_ret = (BT_Node) a->alloc();
	
	BT_ret->data = data;
	BT_ret->sons[LEFT] = left;
	BT_ret->sons[RIGHT] = right; 
	BT_ret->parent = parent;
	
	if( parent != BT_NULL)
		( dir == LEFT )? (parent->sons[LEFT] = BT_ret) : (parent->sons[RIGHT] = BT_ret);
	if ( left != BT_NULL )
		left->parent = BT_ret;
	if (right != BT_NULL )
		right->parent =BT_ret;
	return BT_ret;	
}

BinaryTree BT_NewRoot(BinaryTree a, BT_Node root){
	if (a == NULL ) a=BT_New();
	a->root=root;
	return a;
}

BinaryTree BT_NewAllocator(BinaryTree a, BT_Allocator alloc, BT_Deallocator dealloc){
	if ( a == NULL) a=BT_New();
	a->alloc=alloc;
	a->dealloc=dealloc;
	return a;
}

static void BT_FreeNodeR(BT_Node a, BT_Deallocator dealloc){
	if( a == BT_NULL )
		return;
	
	BT_FreeNodeR( a->sons[LEFT], dealloc);
	BT_FreeNodeR( a->sons[RIGHT], dealloc);
	
	if (dealloc)
		dealloc(a->data );
	free(a);
}

void BT_Free(BinaryTree a){	
	if (!a) return;
	
	BT_FreeNodeR( a->root, a->dealloc );
	free(a);
	return ;
}

BT_Sons BT_FreeNode(BinaryTree tr, BT_Node a){
	BT_Sons S_ret = (BT_Sons) malloc(2*sizeof(BT_Node));
	
	S_ret[ LEFT] = a->sons[ LEFT];
	S_ret[ RIGHT] = a->sons[ RIGHT];
	
	if( tr->dealloc )
		tr->dealloc(a->data);
	if ( a->sons[LEFT] != BT_NULL)
		a->sons[LEFT]->parent = BT_NULL;
	if ( a->sons[LEFT] != BT_NULL )
		a->sons[RIGHT]->parent = BT_NULL;
	
	if (a->parent)
		(a->parent->sons[LEFT] == a)? 
	(a->parent->sons[LEFT] = BT_NULL): (a->parent->sons[RIGHT] = BT_NULL);
	
	return S_ret; 
	
}

/**
 * Memeber access functions
 */

int  BT_Root(BT_Node a){
	if( a == BT_NULL) return INVALID;
	return (a->parent == BT_NULL);	
}

int BT_Leaf(BT_Node a){
	if( a == BT_NULL) return INVALID;
	return ( a->sons[LEFT] == BT_NULL || a->sons[RIGHT] == BT_NULL);
}


int BT_Empty(BinaryTree a){
	return a == NULL || a->root == BT_NULL;
}


int BT_Size(BT_Node a){
	int r_size,l_size;
	if( a == BT_NULL) return 0;

	r_size = BT_Size( a->sons[LEFT]);
	l_size = BT_Size( a->sons[RIGHT]);

	return 1+(r_size >l_size? r_size: l_size);
}


void BT_SetRSon(BT_Node a, BT_Node RSon) {	
	if ( a == BT_NULL ) return ;
	
	a->sons[RIGHT]=RSon;
	if ( RSon != BT_NULL)
		RSon->parent = a;	
}


void BT_SetLSon(BT_Node a, BT_Node LSon){
	if( a == BT_NULL) return ;
	
	a->sons[LEFT]=LSon;
	if ( LSon != BT_NULL)
		LSon->parent=a;
}

void BT_SetP(BT_Node a, BT_Node parent, int dir){
	if ( a ==  BT_NULL) return ;

	a->parent=parent;
	if (parent != BT_NULL )
	( dir == LEFT)? (parent->sons[LEFT]=a ): ( parent->sons[RIGHT]=a);
}

void * BT_GetKey(BT_Node a){	
	if (a == BT_NULL) return NULL;
	return a->data;
}


BT_Node BT_GetRoot(BinaryTree a){
	if (!a) return BT_NULL;
	return a->root;
}

BT_Node  BT_GetRSon(BT_Node a)
{
	if ( a == BT_NULL)  return BT_NULL;	
	return a->sons[RIGHT];	
}

BT_Node  BT_GetLSon(BT_Node a)
{
	if ( a == BT_NULL) return BT_NULL;	
	return a->sons[LEFT];	
}

BT_Node BT_GetP(BT_Node a){
	if ( a == BT_NULL) return BT_NULL;
	return a->parent;
}


int BT_GetDir(BT_Node a){
	if (a == BT_NULL || a->parent == BT_NULL)   return  INVALID;
	if (a->parent->sons[LEFT] == a) return LEFT;
	if (a->parent->sons[RIGHT] == a) return  LEFT;
	return INVALID;
}

BT_Sons BT_GetSons(BT_Node a){
	if (a == BT_NULL) return NULL;
	
	return a->sons;
}

void  BT_TraverseNode(BT_Node a, int type, BT_Task t){
	if (a == BT_NULL) return;
	
	if (type == PREORDER) 	t(a);
	BT_TraverseNode(a->sons[LEFT], type, t);
	if (type == INORDER) 	t(a);	
	BT_TraverseNode(a->sons[RIGHT], type, t);
	if (type == POSTORDER) t(a);
}

void BT_Traverse(BinaryTree a, int type, BT_Task t){
	if (!a) return;
	
	BT_TraverseNode(a->root, type, t );
}

void afis(BT_Node a){
	if (a != BT_NULL) printf("%d ", *(int *) a->data);
}


/**
 * Funnctions for BinarySearchTree
 */
/*
void BST_Insert(BinaryTree a, void * data){
	BT_Node curent = a->root, rs,ls;
	int * key;	

	while (curent != BT_NULL){
		key=BT_GetKey(curent);
		
		if (*(int *)key == * (int *)data) 
			return;
		if (*(int *)key > *(int *)data ){
			if ( (rs = BT_GetRSon(curent)) == BT_NULL ){
				BT_NewNode(a, data, BT_NULL, BT_NULL, curent, RIGHT);
				return;
			}
			else{
				curent = rs;
			}
		}else if ( *(int *)key < *(int *)data ){
				if( ( ls = BT_GetLSon(curent) ) == BT_NULL){
					BT_NewNode( a, data, BT_NULL, BT_NULL, curent, LEFT);
					return;
				}
				else{
					curent = ls;		
				}
			}
	}
}

BT_Node BST_Succ(BT_Node a){
	BT_Node curent = a, rson, lson; 
		
	
	if( (rson = BT_GetRSon( curent)) != BT_NULL ){
		curent = rson;
		while ( ( lson =BT_GetLSon(curent) ) != BT_NULL ) curent=lson;
		return curent;
	}  
	else{
		while(  BT_GetDir(curent) != RIGHT && curent != BT_NULL  ) curent = BT_GetP(curent);
		return curent; 
	}
}

void BST_Traverse( BinaryTree a){
	BT_Node curent = a->root, lson;
	
	while( (lson = BT_GetLSon(curent)) != BT_NULL ) curent = lson;
	
	do{
		printf("%d ", *(int *) BT_GetKey(curent));
		curent=BST_Succ(curent);
	} while( curent != BT_NULL );
}

BT_Node BT_Creeaza(char * a){
	char * data =(char *)malloc(1);
	int n=strlen(a);
	BT_Node l,r,new;

	*data=a[n/2]-'0';	
	if (strlen(a) <2){
		
		new = BT_NewNode( NULL, data,BT_NULL,BT_NULL, BT_NULL, -1 );	
		return new;
	}

	a[n/2]=0;
	
	l=BT_Creeaza(a);
	if (n/2+1 >= n)
		r=BT_NULL;
	else
		r=BT_Creeaza(&a[n/2]+1);
	new = BT_NewNode(NULL ,data,l,r, BT_NULL, -1 );	
	return new ; 	
}

int main()
{
	BinaryTree t;	
	char * a=strdup("1456789012348");
	
	t=BT_NewRoot(t,BT_Creeaza(a));	

	
	BT_Traverse(t,INORDER,afis );	
	return 0;
}
*/



